package LCR;

public class minWindow {
    public String minWindow(String s, String t) {
        /**
         思路：先将t字符串的字符以及个数保存起来（这里用数组记录），
         然后遍历s字符，利用滑动窗口的思想先找到一个符合条件的字串，然后依次尝试去缩小左边界，寻找最短子串
         */
        //除去特例
        String res = "";
        if(t.length() > s.length()){
            return res;
        }
        //创建60位数组保存t中的字符
        int[] cnt1 = new int[60];
        for(char c : t.toCharArray()){
            cnt1[c - 'A']++;
        }
        //记录一个差值，表示cnt1存在多少字符需要去找
        int diff = 0;
        for(int n : cnt1){
            if(n != 0) diff++;
        }
        //记录好差值，以及存放的数组之后去s字符串中寻找
        int[] cnt2 = new int[60];
        int j = 0; //窗口左边界
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < s.length(); i++){
            //每次遍历都记录下当前的字符以及个数，方便与cnt1进行比较
            int x = s.charAt(i) - 'A';
            cnt2[x]++;
            //判断s中的是否和t中的字符以及个数相等，相等说明找到了一个字符，就消除一个差值
            if(cnt1[x] == cnt2[x]) diff--;
            //如果差值为0，说明在s中找到了t中的全部字符
            while(diff == 0){ //因为是求最短子串，滑动窗口最左边的可能可以移动，所以尝试着去缩小长度
                //统计结果
                int len = i - j + 1;
                if(len < min){
                    min = len;
                    res = s.substring(j, i + 1); //记录当前符合条件的子串
                }
                //尝试着去缩小左边界
                int y = s.charAt(j) - 'A'; //左边界下标
                cnt2[y]--; //减去左边界的字符
                j++; //左指针移动
                if(cnt1[y] != 0 && cnt2[y] < cnt1[y]){
                    /**
                     cnt1[y] != 0 说明t字符串中存在这个左边界的字符，如果移动会导致差值改变
                     cnt2[y] < cnt1[y] 表示s字符串中的这个字符不足以满足t字符串所需要的
                     只有上面两个同时成立，差异才会产生
                     */
                    diff++;
                }
                //如果差异一直为0说明可以一直缩小长度，取最优
            }
        }
        return res;
    }
}
